#ifndef JEGEO_POLYCOLLISION_HPP
#define JEGEO_POLYCOLLISION_HPP
#include "jegeo/common.hpp"
#include "jegeo/math.hpp"
#include "jegeo/boostadaptor.hpp"
#include <QDebug>

namespace jegeo {

namespace jemath = jegeo::math;

namespace polycollision_internal {
/*
* 判断点是否在矩形边上
*/
template<typename T>
bool is_point_on_rect_edges(const Point<T> &point, const Rect<T> &rect) {
    T px = jegeo::px(point);
    T py = jegeo::py(point);
    T rminx = jemath::jemin(jegeo::px1(rect), jegeo::px2(rect));
    T rmaxx = jemath::jemax(jegeo::px1(rect), jegeo::px2(rect));
    T rminy = jemath::jemin(jegeo::py1(rect), jegeo::py2(rect));
    T rmaxy = jemath::jemax(jegeo::py1(rect), jegeo::py2(rect));

    if ((jemath::fuzzy_equal(px, rminx) or jemath::fuzzy_equal(px, rmaxx))
            && jemath::fuzzy_greaterequal(py, rminy) && jemath::fuzzy_lessequal(py, rmaxy)) {
        return true;
    } else if ((jemath::fuzzy_equal(py, rminy) or jemath::fuzzy_equal(py, rmaxy))
               && jemath::fuzzy_greaterequal(px, rminx) && jemath::fuzzy_lessequal(px, rmaxx)) {
        return true;
    }

    return false;
}

/*
* 点到点的距离
*/
template<typename T>
T distance_point2point(const Point<T> &ps, const Point<T> &pe)
{
    return jemath::jehypot(jegeo::px(pe) - jegeo::px(ps), jegeo::py(pe) - jegeo::py(ps));
}

/*
* 点到直线的距离
*/
template<typename T>
T distance_point2line(const Point<T> &point, const Line<T> &line) {
    T length = line::get_length(line);
    T lx = jegeo::pex(line) - jegeo::psx(line);
    T ly = jegeo::pey(line) - jegeo::psy(line);
    T vx = jegeo::px(point) - jegeo::psx(line);
    T vy = jegeo::py(point) - jegeo::psy(line);
    T dis = jemath::jediv(jemath::jeabs(jemath::jemul(vx, ly) - jemath::jemul(lx, vy)), length);

    return dis;
}

/*
* 点到线段的距离
*/
template<typename T>
T distance_point2segment(const Point<T> &point, const Line<T> &line)
{
    T length = line::get_length(line);
    T lx = jegeo::pex(line) - jegeo::psx(line);
    T ly = jegeo::pey(line) - jegeo::psy(line);
    T vx = jegeo::px(point) - jegeo::psx(line);
    T vy = jegeo::py(point) - jegeo::psy(line);
    T dis = jemath::jediv(jemath::jeabs(jemath::jemul(vx, ly) - jemath::jemul(lx, vy)), length);

    // 点到线段的距离
    T dot_product_s = jemath::jemul(vx, lx) + jemath::jemul(vy, ly);
    if (dot_product_s < 0) {
        return distance_point2point(point, line::get_ps(line));
    }

    T vex = jegeo::px(point) - jegeo::pex(line);
    T vey = jegeo::py(point) - jegeo::pey(line);
    T rlx = -lx;
    T rly = -ly;

    T dot_project_e = jemath::jemul(vex, rlx) + jemath::jemul(vey, rly);
    if (dot_project_e < 0) {
        return distance_point2point(point, line::get_pe(line));
    }

    return dis;
}

/*
* 点到单调弧的距离
*/
template<typename T>
T distance_point2monarc(const Point<T> &point, const Arc<T> &arc)
{
    T radius = arc::get_radius(arc);
    T dpc = distance_point2point(point, arc::get_pc(arc));
    T uvx = jemath::jediv(jegeo::px(point) - jegeo::pcx(arc), dpc);
    T uvy = jemath::jediv(jegeo::py(point) - jegeo::pcy(arc), dpc);
    T cx = jegeo::pcx(arc) + jemath::jemul(uvx, radius);
    T cy = jegeo::pcy(arc) + jemath::jemul(uvy, radius);

    T aminx = jemath::jemin(jegeo::psx(arc), jegeo::pex(arc));
    T amaxx = jemath::jemax(jegeo::psx(arc), jegeo::pex(arc));
    T aminy = jemath::jemin(jegeo::psy(arc), jegeo::pey(arc));
    T amaxy = jemath::jemax(jegeo::psy(arc), jegeo::pey(arc));
    if (cx < aminx || cx > amaxx || cy < aminy || cy > amaxy) {
        T d1 = distance_point2point(point, arc::get_ps(arc));
        T d2 = distance_point2point(point, arc::get_pe(arc));
        return jemath::jemin(d1, d2);
    }

    return distance_point2point(point, point::make(cx, cy));
}

/*
* 判断矩形 a 是否被包含在矩形 b 里面
*/
template<typename T>
inline bool contains_rect_in_rect(const Rect<T> &rect_a, const Rect<T> &rect_b, bool consider_touch = true) {
    return jemath::contains_rect_in_rect(jegeo::px1(rect_a), jegeo::py1(rect_a), jegeo::px2(rect_a), jegeo::py2(rect_a),
                                         jegeo::px1(rect_b), jegeo::py1(rect_b), jegeo::px2(rect_b), jegeo::py2(rect_b), consider_touch);
}

/*
* 判断点是否被包含在矩形里面
*/
template<typename T>
inline bool contains_point_in_rect(const Point<T> &point, const Rect<T> &rect, bool consider_touch = true) {
    return jemath::contains_point_in_rect(jegeo::px(point), jegeo::py(point),
                                          jegeo::px1(rect), jegeo::py1(rect), jegeo::px2(rect), jegeo::py2(rect), consider_touch);
}

/*
* 判断线段与线段是否相交
*/
template<typename T>
inline bool intersects_segment2segment(const Line<T> &line_1, const Line<T> &line_2, bool consider_touch = true) {
    return jemath::intersects_segment2segment(jegeo::psx(line_1), jegeo::psy(line_1), jegeo::pex(line_1), jegeo::pey(line_1),
                                              jegeo::psx(line_2), jegeo::psy(line_2), jegeo::pex(line_2), jegeo::pey(line_2), consider_touch);
}

/*
* 判断线段与单调弧是否相交
*/
template<typename T>
inline bool intersects_segment2monarc(const Line<T> &line, const Arc<T> &arc, bool consider_touch = true) {
    return jemath::intersects_segment2monarc(jegeo::psx(line), jegeo::psy(line), jegeo::pex(line), jegeo::pey(line),
                                             jegeo::psx(arc), jegeo::psy(arc), jegeo::pex(arc), jegeo::pey(arc),
                                             jegeo::pcx(arc), jegeo::pcy(arc), arc::get_radius(arc), consider_touch);
}

/*
* 判断单调弧和单调弧是否相交
*/
template<typename T>
inline bool intersects_monarc2monarc(const Arc<T> &arc_1, const Arc<T> &arc_2, bool consider_touch = true) {
    return jemath::intersects_monarc2monarc(jegeo::psx(arc_1), jegeo::psy(arc_1), jegeo::pex(arc_1), jegeo::pey(arc_1), jegeo::pcx(arc_1), jegeo::pcy(arc_1), arc::get_radius(arc_1),
                                            jegeo::psx(arc_2), jegeo::psy(arc_2), jegeo::pex(arc_2), jegeo::pey(arc_2), jegeo::pcx(arc_2), jegeo::pcy(arc_2), arc::get_radius(arc_2),
                                            consider_touch);
}

/*
* 判断矩形和单调弧是否相交
*/
template<typename T>
inline bool intersects_rect2monarc(const Rect<T> &rect, const Arc<T> &arc, bool consider_touch = true) {
    return jemath::intersects_rect2monarc(jegeo::px1(rect), jegeo::py1(rect), jegeo::px2(rect), jegeo::py2(rect),
                                          jegeo::psx(arc), jegeo::psy(arc), jegeo::pex(arc), jegeo::pey(arc),
                                          jegeo::pcx(arc), jegeo::pcy(arc), arc::get_radius(arc), consider_touch);
}

template<typename T>
inline bool intersects_rect2rect(const Rect<T> &rect_a, const Rect<T> &rect_b, bool consider_touch = true) {
    return jemath::intersects_rect2rect(jegeo::px1(rect_a), jegeo::py1(rect_a), jegeo::px2(rect_a), jegeo::py2(rect_a),
                                        jegeo::px1(rect_b), jegeo::py1(rect_b), jegeo::px2(rect_b), jegeo::py2(rect_b), consider_touch);
}

/*
* 获取向右水平射线和单调弧的交点
*/
template<typename T>
inline bool intersection_rray2monarc(const Point<T> &ray, const Arc<T> &arc, Point<T> &inter_point, bool consider_touch = true) {
    T interx, intery;
    if (jemath::intersection_rray2monarc(jegeo::px(ray), jegeo::py(ray),
                                         jegeo::psx(arc), jegeo::psy(arc), jegeo::pex(arc), jegeo::pey(arc),
                                         jegeo::pcx(arc), jegeo::pcy(arc), arc::get_radius(arc),
                                         interx, intery)) {
        if (consider_touch) {
            jegeo::set_px(inter_point, interx);
            jegeo::set_py(inter_point, intery);
            return true;
        } else if (jemath::fuzzy_notequal(interx, jegeo::px(ray))
                   && jemath::fuzzy_notequal(intery, jegeo::py(ray))
                   && jemath::fuzzy_notequal(interx, jegeo::psx(arc))
                   && jemath::fuzzy_notequal(interx, jegeo::pex(arc))) {
            return true;
        }
    }

    return false;
}

/*
* 获取向右水平射线和直线段的交点
*/
template<typename T>
inline bool intersection_rray2segment(const Point<T> &ray, const Line<T> &seg, Point<T> &inter_point, bool consider_touch = true) {
    T interx, intery;
    if (jemath::intersection_rray2segment(jegeo::px(ray), jegeo::py(ray),
                                         jegeo::psx(seg), jegeo::psy(seg), jegeo::pex(seg), jegeo::pey(seg),
                                         interx, intery)) {
        if (consider_touch) {
            jegeo::set_px(inter_point, interx);
            jegeo::set_py(inter_point, intery);
            return true;
        } else if (jemath::fuzzy_notequal(interx, jegeo::px(ray))
                   && jemath::fuzzy_notequal(intery, jegeo::py(ray))
                   && jemath::fuzzy_notequal(interx, jegeo::psx(seg))
                   && jemath::fuzzy_notequal(interx, jegeo::pex(seg))) {
            return true;
        }
    }

    return false;
}

/*
* 获取矩形和矩形的交集
*/
template<typename T>
inline bool intersection_rect2rect(const Rect<T> &recta, const Rect<T> &rectb, Rect<T> &inter_rect) {
    T inter_x1, inter_y1, inter_x2, inter_y2;
    if (jemath::intersection_rect2rect(jegeo::px1(recta), jegeo::py1(recta), jegeo::px2(recta), jegeo::py2(recta),
                                       jegeo::px1(rectb), jegeo::py1(rectb), jegeo::px2(rectb), jegeo::py2(rectb),
                                       inter_x1, inter_y1, inter_x2, inter_y2)) {
        jegeo::set_px1(inter_rect, inter_x1);
        jegeo::set_py1(inter_rect, inter_y1);
        jegeo::set_px2(inter_rect, inter_x2);
        jegeo::set_py2(inter_rect, inter_y2);
        return true;
    }
    return false;
}

/*
* 判断一个点是否在一个 polygon 里面
*/
template<typename T>
bool is_point_in_polygon(const Point<T> &point,
                        const Polygon<T> &polygon,
                        const Rect<T> &poly_bbox,
                        const std::vector<Edge<T>> &polySegs,
                        const jegeo::bmodel::BBoxRTree<T> &polyRtree,
                        bool consider_touch = true,
                        bool check_contains = true)
{
    if (check_contains && !contains_point_in_rect(point, poly_bbox, consider_touch)) {
        return false;
    }

    std::vector<Edge<T>> segList;
    for (auto seg : polySegs) {
        if (jegeo::psy(seg) < jegeo::pey(seg)) {
            edge::reverse(seg);
        }
        segList.push_back(seg);
    }

    jegeo::bmodel::BSegment<T> ray = jegeo::segment::to_bsegment(point, point::make(std::numeric_limits<T>::max(), jegeo::py(point)));
    jegeo::bmodel::BBoxResults<T> result_sids;
    polyRtree.query(bgi::intersects(ray), std::back_inserter(result_sids));

    int intersectCount = 0;
    for (const auto &sid : result_sids) {
        auto seg = segList[sid.second];
        if (edge::is_line(seg) && jemath::fuzzy_equal(jegeo::psy(seg), jegeo::pey(seg))) {
            continue;
        }

        if (jemath::fuzzy_notequal(jegeo::py(point), jegeo::pey(seg))) {
            auto bbox = edge::get_bound_rect(seg);
            if (contains_point_in_rect(point, edge::get_bound_rect(seg), true)) {
                if (edge::is_arc(seg)) {
                    Arc<T> tmp_arc = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
                    Point<T> inter_point;
                    if (intersection_rray2monarc(point, tmp_arc, inter_point, true)) {
                        // point 沿 x 轴正方形的射线与弧线存在交点
                        if (jegeo::px(inter_point) == jegeo::px(point)) {
                            // point 在多边形的边上
                            if (consider_touch) {
                                return true;
                            } else {
                                return false;
                            }
                        }
                        intersectCount++;
                    }
                } else if (edge::is_line(seg)) {
                    auto tmp_line = line::make(edge::get_ps(seg), edge::get_pe(seg));
                    Point<T> inter_point;
                    if (intersection_rray2segment(point, tmp_line, inter_point, true)) {
                        // point 沿 x 轴正方形的射线与直线段存在交点
                        if (jegeo::px(inter_point) == jegeo::px(point)) {
                            // point 在多边形的边上
                            if (consider_touch) {
                                return true;
                            } else {
                                return false;
                            }
                        }
                        intersectCount++;
                    }
                }
            } else {
                intersectCount++;
            }
        }
    }

    if (intersectCount % 2 == 1) {
        return true;
    }
    return false;
}


/*
* 判断一个点是否在一个 polygon 里面
*/
template<typename T>
bool is_point_in_polygon(const Point<T> &point,const Polygon<T> &polygon, const Rect<T> &poly_bbox, bool consider_touch = true)
{
    if (!contains_point_in_rect(point, poly_bbox, consider_touch)) {
        return false;
    }

    // 构建 rtree
    std::vector<Edge<T>> segList;
    for (Edge<T> &seg : polygon::get_edges(polygon, true)) {
        if (jegeo::psy(seg) < jegeo::pey(seg)) {
            edge::reverse(seg);
        }
        if (edge::is_line(seg) && jemath::fuzzy_equal(jegeo::psy(seg), jegeo::pey(seg))) {
            continue;
        }
        segList.push_back(seg);
    }

    jegeo::bmodel::BBoxRTree<T> rtree = jegeo::rtree::create_box_rtree(segList);
    return is_point_in_polygon(point, polygon, poly_bbox, segList, rtree, consider_touch, false);
}

/*
* 指定一个 polygon_a 的 rect 区域, 判断该区域中是否存在一个点在另一个 polygon_b 里面, ppoly_Result 保存 polygon_a 的 rtree 查询结果
*/
template<typename T>
bool is_point_in_polygon_from_rect(const jegeo::bmodel::BBox<T> &ppoly_rect,
                                   const Polygon<T> &polygon,
                                   const std::vector<Edge<T>> &ppoly_segs,
                                   const jegeo::bmodel::BBoxRTree<T> &ppoly_rtree,
                                   const std::vector<Edge<T>> &poly_segs,
                                   const jegeo::bmodel::BBoxRTree<T> &poly_rtree,
                                   jegeo::bmodel::BBoxResults<T> &ppoly_Result,
                                   bool consider_touch = true)
{
    ppoly_rtree.query(bgi::intersects(ppoly_rect), std::back_inserter(ppoly_Result));
    // 判断相交区域中是否有点包含在对方里面
    const auto &poly_bbox = polygon::get_bound_rect(polygon);
    for (int i = 0; i < ppoly_Result.size(); i++) {
        auto sid = ppoly_Result[i];
        auto seg = ppoly_segs[sid.second];
        if (is_point_in_polygon(edge::get_ps(seg), polygon, poly_bbox, poly_segs, poly_rtree, consider_touch)) {
            return true;
        } else if (is_point_in_polygon(edge::get_pe(seg), polygon, poly_bbox, poly_segs, poly_rtree, consider_touch)) {
            return true;
        }
    }
    return false;
}

/*
* 判断一个 segment 是否在 polygon 里面
*/
template<typename T>
bool is_segment_in_polygon(const Edge<T> &segment,
                           const Polygon<T> &polygon,
                           const std::vector<Edge<T>> &poly_segs,
                           const jegeo::bmodel::BBoxRTree<T> &poly_rtree,
                           bool consider_touch = true)
{
    const auto &poly_bbox = polygon::get_bound_rect(polygon);
    // 判断端点是否在 polygon 中
    if (!is_point_in_polygon(edge::get_ps(segment), polygon, poly_bbox, poly_segs, poly_rtree, consider_touch)) {
        return false;
    }
    if (!is_point_in_polygon(edge::get_pe(segment), polygon, poly_bbox, poly_segs, poly_rtree, consider_touch)) {
        return false;
    }

    // 判断当前直线或者弧线是否在 polygon 中
    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(edge::get_bound_rect(segment));
    jegeo::bmodel::BBoxResults<T> result_sids;
    poly_rtree.query(bgi::intersects(query_box), std::back_inserter(result_sids));

    for (const auto &sid : result_sids) {
        auto seg = poly_segs[sid.second];
        if (edge::is_line(seg) && edge::is_line(segment)) {
            Line<T> tmp_line_1 = line::make(edge::get_ps(seg), edge::get_pe(seg));
            Line<T> tmp_line_2 = line::make(edge::get_ps(segment), edge::get_pe(segment));
            if (intersects_segment2segment(tmp_line_1, tmp_line_2, consider_touch)) {
                return false;
            }
        } else if (edge::is_line(seg) && edge::is_arc(segment)) {
            Line<T> tmp_line = line::make(edge::get_ps(seg), edge::get_pe(seg));
            Arc<T> tmp_arc = arc::make(edge::get_ps(segment), edge::get_pe(segment), edge::get_angle(segment));
            if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                return false;
            }
        } else if (edge::is_arc(seg) && edge::is_line(segment)) {
            Line<T> tmp_line = line::make(edge::get_ps(segment), edge::get_pe(segment));
            Arc<T> tmp_arc = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                return false;
            }
        } else if (edge::is_arc(seg) && edge::is_arc(segment)) {
            Arc<T> tmp_arc_1 = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            Arc<T> tmp_arc_2 = arc::make(edge::get_ps(segment), edge::get_pe(segment), edge::get_angle(segment));
            if (intersects_monarc2monarc(tmp_arc_1, tmp_arc_2, consider_touch)) {
                return false;
            }
        }
    }

    return true;
}

/*
* 判断一个 segment 是否在 polygon 里面
*/
template<typename T>
bool is_segment_in_polygon(const Edge<T> &segment, const Polygon<T> &polygon, bool consider_touch = true)
{
    // polygon 构建树
    std::vector<Edge<T>> segList;
    for (const auto &seg : polygon::get_edges(polygon, true)) {
        segList.push_back(seg);
    }
    jegeo::bmodel::BBoxRTree<T> rtree = jegeo::rtree::create_box_rtree(segList);

    const auto &poly_bbox = polygon::get_bound_rect(polygon);
    // 判断端点是否在 polygon 中
    if (!is_point_in_polygon(edge::get_ps(segment), polygon, poly_bbox, segList, rtree, consider_touch)) {
        return false;
    }
    if (!is_point_in_polygon(edge::get_pe(segment), polygon, poly_bbox, segList, rtree, consider_touch)) {
        return false;
    }

    // 判断当前直线或者弧线是否在 polygon 中
    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(edge::get_bound_rect(segment));
    jegeo::bmodel::BBoxResults<T> result_sids;
    rtree.query(bgi::intersects(query_box), std::back_inserter(result_sids));

    for (const auto &sid : result_sids) {
        auto seg = segList[sid.second];
        if (edge::is_line(seg) && edge::is_line(segment)) {
            Line<T> tmp_line_1 = line::make(edge::get_ps(seg), edge::get_pe(seg));
            Line<T> tmp_line_2 = line::make(edge::get_ps(segment), edge::get_pe(segment));
            if (intersects_segment2segment(tmp_line_1, tmp_line_2, consider_touch)) {
                return false;
            }
        } else if (edge::is_line(seg) && edge::is_arc(segment)) {
            Line<T> tmp_line = line::make(edge::get_ps(seg), edge::get_pe(seg));
            Arc<T> tmp_arc = arc::make(edge::get_ps(segment), edge::get_pe(segment), edge::get_angle(segment));
            if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                return false;
            }
        } else if (edge::is_arc(seg) && edge::is_line(segment)) {
            Line<T> tmp_line = line::make(edge::get_ps(segment), edge::get_pe(segment));
            Arc<T> tmp_arc = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                return false;
            }
        } else if (edge::is_arc(seg) && edge::is_arc(segment)) {
            Arc<T> tmp_arc_1 = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            Arc<T> tmp_arc_2 = arc::make(edge::get_ps(segment), edge::get_pe(segment), edge::get_angle(segment));
            if (intersects_monarc2monarc(tmp_arc_1, tmp_arc_2, consider_touch)) {
                return false;
            }
        }
    }

    return true;
}

/*
* 提供给判断矩形和 polygon 是否碰撞使用的函数, 请勿直接使用
*/
template<typename T>
bool intersects_rect2polygon_line(const Rect<T> &rect,
                                  const jegeo::bmodel::BBox<T> &query_box,
                                  const std::vector<Edge<T>> &polyLineSegs,
                                  const jegeo::bmodel::BSegmentRTree<T> &polyLineRtree,
                                  bool consider_touch = true)
{
    // 获取碰撞到的线段
    jegeo::bmodel::BSegmentResults<T> result_sids;
    polyLineRtree.query(bgi::intersects(query_box), std::back_inserter(result_sids));

    if (consider_touch) {
        if (!result_sids.empty()) {
            return true;
        }
    } else {
        if (!result_sids.empty()) {
            for (const auto &sid : result_sids) {
                Edge<T> seg = polyLineSegs[sid.second];
                if (is_point_on_rect_edges(edge::get_ps(seg), rect)) {
                    return false;
                }
                if (is_point_on_rect_edges(edge::get_pe(seg), rect)) {
                    return false;
                }
            }
            return true;
        }
    }

    return false;
}


/*
* 提供给判断矩形和 polygon 是否碰撞使用的函数, 请勿直接使用
*/
template<typename T>
bool intersects_rect2polygon_monarc(const Rect<T> &rect,
                                    const jegeo::bmodel::BBox<T> &query_box,
                                    const std::vector<Edge<T>> &polyArcSegs,
                                    const jegeo::bmodel::BBoxRTree<T> &polyArcRtee,
                                    bool consider_touch = true)
{
    // 获取可能碰撞到的弧
    jegeo::bmodel::BBoxResults<T> result_sids;
    polyArcRtee.query(bgi::intersects(query_box), std::back_inserter(result_sids));

    if (!result_sids.empty()) {
        for (const auto &sid : result_sids) {
            auto seg = polyArcSegs[sid.second];
            Arc<T> arc = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            if (intersects_rect2monarc(rect, arc, consider_touch)) {
                return true;
            }
        }
    }
    return false;
}

}  // internal

namespace intersects {
using namespace polycollision_internal;

/*
* 判断圆和 polygon 是否相交
*/
template<typename T>
bool cicle2polygon(const Circle<T> &cicle,
                              const Polygon<T> &polygon,
                              const std::vector<Edge<T>> &poly_segs,
                              const jegeo::bmodel::BBoxRTree<T> &poly_rtree,
                              bool consider_touch = true)
{
    Point<T> pc = circle::get_pc(cicle);
    T radius = circle::get_radius(cicle);
    Rect<T> tRect = rect::make(point::make(jegeo::px(pc) - radius, jegeo::py(pc) - radius), point::make(jegeo::px(pc) + radius, jegeo::py(pc) + radius));
    Rect<T> pRect = polygon::get_bound_rect(polygon);

    if (!intersects_rect2rect(tRect, pRect, consider_touch)) {
        return false;
    }

    // 构建 rtree
    jegeo::bmodel::BBoxResults<T> result_sids;
    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(tRect);
    poly_rtree.query(bgi::intersects(query_box), std::back_inserter(result_sids));

    for (const auto &sid : result_sids) {
        auto seg = poly_segs[sid.second];
        if (edge::is_line(seg)) {
            Line<T> line = line::make(edge::get_ps(seg), edge::get_pe(seg));
            if (consider_touch && jemath::fuzzy_lessequal(distance_point2segment(pc, line), radius)) {
                return true;
            } else if (!consider_touch && distance_point2segment(pc, line) < radius) {
                return true;
            }
        } else if (edge::is_arc(seg)) {
            Arc<T> arc = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            if (consider_touch && jemath::fuzzy_lessequal(distance_point2monarc(pc, arc), radius)) {
                return true;
            } else if (!consider_touch && distance_point2monarc(pc, arc) < radius) {
                return true;
            }
        }
    }

    return false;
}

/*
* 判断圆和 polygon 是否相交
*/
template<typename T>
bool cicle2polygon(const Circle<T> &cicle, const Polygon<T> &polygon, bool consider_touch = true)
{
    Point<T> pc = circle::get_pc(cicle);
    T radius = circle::get_radius(cicle);
    Rect<T> tRect = rect::make(point::make(jegeo::px(pc) - radius, jegeo::py(pc) - radius), point::make(jegeo::px(pc) + radius, jegeo::py(pc) + radius));
    Rect<T> pRect = polygon::get_bound_rect(polygon);

    if (!intersects_rect2rect(tRect, pRect, consider_touch)) {
        return false;
    }

    // 构建 rtree
    std::vector<Edge<T>> segList;
    for (auto &seg : polygon::get_edges(polygon, true)) {
        segList.push_back(seg);
    }

    jegeo::bmodel::BBoxRTree<T> rtree = jegeo::rtree::create_box_rtree(segList);
    jegeo::bmodel::BBoxResults<T> result_sids;
    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(tRect);
    rtree.query(bgi::intersects(query_box), std::back_inserter(result_sids));

    for (const auto &sid : result_sids) {
        auto seg = segList[sid.second];
        if (edge::is_line(seg)) {
            Line<T> line = line::make(edge::get_ps(seg), edge::get_pe(seg));
            if (consider_touch && jemath::fuzzy_lessequal(distance_point2segment(pc, line), radius)) {
                return true;
            } else if (!consider_touch && distance_point2segment(pc, line) < radius) {
                return true;
            }
        } else if (edge::is_arc(seg)) {
            Arc<T> arc = arc::make(edge::get_ps(seg), edge::get_pe(seg), edge::get_angle(seg));
            if (consider_touch && jemath::fuzzy_lessequal(distance_point2monarc(pc, arc), radius)) {
                return true;
            } else if (!consider_touch && distance_point2monarc(pc, arc) < radius) {
                return true;
            }
        }
    }

    return false;
}

/*
* 判断矩形和 polygon 是否相交
*/
template<typename T>
bool rect2polygon(const Rect<T> &rect, const Polygon<T> &polygon, bool consider_touch = true)
{
    Rect<T> tRect = rect;
    Rect<T> pRect = polygon::get_bound_rect(polygon);

    if (!intersects_rect2rect(tRect, pRect, consider_touch)) {
        return false;
    }

    if (contains_rect_in_rect(pRect, tRect, consider_touch)) {
        return true;
    }

    // 构造 rtree
    std::vector<Edge<T>> segLineList;
    std::vector<Edge<T>> segArcList;
    std::vector<Edge<T>> segList;
    for (auto seg : polygon::get_edges(polygon, true)) {
        if (edge::is_line(seg)) {
            segLineList.push_back(seg);
        } else if (edge::is_arc(seg)) {
            segArcList.push_back(seg);
        }
        segList.push_back(seg);
    }

    if (contains_rect_in_rect(tRect, pRect) && !segList.empty()) {
        jegeo::bmodel::BBoxRTree<T> rtree = jegeo::rtree::create_box_rtree(segList);
        const auto &poly_bbox = polygon::get_bound_rect(polygon);
        if (is_point_in_polygon(rect::get_p1(tRect), polygon, poly_bbox, segList, rtree, consider_touch)) {
            return true;
        }
        if (is_point_in_polygon(rect::get_p2(tRect), polygon, poly_bbox, segList, rtree, consider_touch)) {
            return true;
        }
        if (is_point_in_polygon(point::make(jegeo::px1(tRect), jegeo::py2(tRect)), polygon, poly_bbox, segList, rtree, consider_touch)) {
            return true;
        }
        if (is_point_in_polygon(point::make(jegeo::px2(tRect), jegeo::py1(tRect)), polygon, poly_bbox, segList, rtree, consider_touch)) {
            return true;
        }
    }

    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(tRect);
    if (!segLineList.empty()) {
        // 获取碰撞到的线段
        jegeo::bmodel::BSegmentRTree<T> rtree = jegeo::rtree::create_segment_rtree(segLineList);
        if (intersects_rect2polygon_line(tRect, query_box, segLineList, rtree, consider_touch)) {
            return true;
        }
    }

    if (!segArcList.empty()) {
        // 获取可能碰撞到的弧
        jegeo::bmodel::BBoxRTree<T> rtree = jegeo::rtree::create_box_rtree(segArcList);
        return intersects_rect2polygon_monarc(tRect, query_box, segArcList, rtree, consider_touch);
    }

    return false;
}

/*
* 判断矩形和 polygon 是否相交
*/
template<typename T>
bool rect2polygon(const Rect<T> &rect,
                             const Polygon<T> &polygon,
                             const std::vector<Edge<T>> &all_poly_segs,
                             const jegeo::bmodel::BBoxRTree<T> &all_poly_rtree,
                             const std::vector<Edge<T>> &line_poly_segs,
                             const jegeo::bmodel::BSegmentRTree<T> &line_poly_rtree,
                             const std::vector<Edge<T>> &arc_poly_segs,
                             const jegeo::bmodel::BBoxRTree<T> &arc_poly_rtree,
                             bool consider_touch = true)
{
    Rect<T> tRect = rect;
    Rect<T> pRect = polygon::get_bound_rect(polygon);

    if (!intersects_rect2rect(tRect, pRect, consider_touch)) {
        return false;
    }

    if (contains_rect_in_rect(pRect, tRect, consider_touch)) {
        return true;
    }

    if (contains_rect_in_rect(tRect, pRect) && !all_poly_segs.empty()) {
        const auto &poly_bbox = polygon::get_bound_rect(polygon);
        if (is_point_in_polygon(rect::get_p1(tRect), polygon, poly_bbox, all_poly_segs, all_poly_rtree, consider_touch)) {
            return true;
        }
        if (is_point_in_polygon(rect::get_p2(tRect), polygon, poly_bbox, all_poly_segs, all_poly_rtree, consider_touch)) {
            return true;
        }
        if (is_point_in_polygon(point::make(jegeo::px1(tRect), jegeo::py2(tRect)), polygon, poly_bbox, all_poly_segs, all_poly_rtree, consider_touch)) {
            return true;
        }
        if (is_point_in_polygon(point::make(jegeo::px2(tRect), jegeo::py1(tRect)), polygon, poly_bbox, all_poly_segs, all_poly_rtree, consider_touch)) {
            return true;
        }
    }

    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(tRect);
    if (!line_poly_segs.empty() && intersects_rect2polygon_line(tRect, query_box, line_poly_segs, line_poly_rtree, consider_touch)) {
        return true;
    }

    if (!arc_poly_segs.empty()) {
        return intersects_rect2polygon_monarc(tRect, query_box, arc_poly_segs, arc_poly_rtree, consider_touch);
    }

    return false;
}

/*
* 判断 polygon 和 polygon 是否相交
*/
template<typename T>
bool polygon2polygon(const Polygon<T> &polygon_a,
                                const Polygon<T> &polygon_b,
                                const std::vector<Edge<T>> &polya_segs,
                                const jegeo::bmodel::BBoxRTree<T> &polya_rtree,
                                const std::vector<Edge<T>> &polyb_segs,
                                const jegeo::bmodel::BBoxRTree<T> &polyb_rtree,
                                bool consider_touch = true)
{
    Rect<T> tRect = polygon::get_bound_rect(polygon_a);
    Rect<T> pRect = polygon::get_bound_rect(polygon_b);

    Rect<T> inter_rect;
    if (!intersection_rect2rect(tRect, pRect, inter_rect)) {
        return false;
    }
    if (!consider_touch && (jemath::fuzzy_equal(jegeo::px1(inter_rect), jegeo::px2(inter_rect))
                            || jemath::fuzzy_equal(jegeo::py1(inter_rect), jegeo::py2(inter_rect)))) {
        return false;
    }
    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(inter_rect);

    jegeo::bmodel::BBoxResults<T> trResultSids;
    if (is_point_in_polygon_from_rect(query_box, polygon_a, polya_segs, polya_rtree, polyb_segs, polyb_rtree, trResultSids, consider_touch)) {
        return true;
    }

    jegeo::bmodel::BBoxResults<T> prResultSids;
    if (is_point_in_polygon_from_rect(query_box, polygon_b, polyb_segs, polyb_rtree, polya_segs, polya_rtree, prResultSids, consider_touch)) {
        return true;
    }

    // 都没有点在对方多边形里面的话, 判断重合区域的双方是否有线段相交
    for (const auto &psid : prResultSids) {
        auto segp = polyb_segs[psid.second];
        for (const auto &tsid : trResultSids) {
            auto segt = polya_segs[tsid.second];
            if (edge::is_line(segp) && edge::is_line(segt)) {
                Line<T> tmp_line_1 = line::make(edge::get_ps(segp), edge::get_pe(segp));
                Line<T> tmp_line_2 = line::make(edge::get_ps(segt), edge::get_pe(segt));
                if (intersects_segment2segment(tmp_line_1, tmp_line_2, consider_touch)) {
                    return true;
                }
            } else if (edge::is_line(segp) && edge::is_arc(segt)) {
                Line<T> tmp_line = line::make(edge::get_ps(segp), edge::get_pe(segp));
                Arc<T> tmp_arc = arc::make(edge::get_ps(segt), edge::get_pe(segt), edge::get_angle(segt));
                if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                    return true;
                }
            } else if (edge::is_arc(segp) && edge::is_line(segt)) {
                Line<T> tmp_line = line::make(edge::get_ps(segt), edge::get_pe(segt));
                Arc<T> tmp_arc = arc::make(edge::get_ps(segp), edge::get_pe(segp), edge::get_angle(segp));
                if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                    return true;
                }
            } else if (edge::is_arc(segp) && edge::is_arc(segt)) {
                Arc<T> tmp_arc_1 = arc::make(edge::get_ps(segp), edge::get_pe(segp), edge::get_angle(segp));
                Arc<T> tmp_arc_2 = arc::make(edge::get_ps(segt), edge::get_pe(segt), edge::get_angle(segt));
                if (intersects_monarc2monarc(tmp_arc_1, tmp_arc_2, consider_touch)) {
                    return true;
                }
            }
        }
    }

    return false;
}

/*
* 判断 polygon 和 polygon 是否相交
*/
template<typename T>
bool polygon2polygon(const Polygon<T> &polygon_a, const Polygon<T> &polygon_b, bool consider_touch = true)
{
    Rect<T> tRect = polygon::get_bound_rect(polygon_a);
    Rect<T> pRect = polygon::get_bound_rect(polygon_b);

    Rect<T> inter_rect;
    if (!intersection_rect2rect(tRect, pRect, inter_rect)) {
        return false;
    }
    if (!consider_touch && (jemath::fuzzy_equal(jegeo::px1(inter_rect), jegeo::px2(inter_rect))
                            || jemath::fuzzy_equal(jegeo::py1(inter_rect), jegeo::py2(inter_rect)))) {
        return false;
    }

    // 构造树
    std::vector<Edge<T>> segTList;
    std::vector<Edge<T>> segPList;
    for (auto seg : polygon::get_edges(polygon_a, true)) {
        segTList.push_back(seg);
    }
    for (auto seg : polygon::get_edges(polygon_b, true)) {
        segPList.push_back(seg);
    }

    if (segTList.empty() || segPList.empty()) {
        return false;
    }

    jegeo::bmodel::BBoxRTree<T> trTree = jegeo::rtree::create_box_rtree(segTList);
    jegeo::bmodel::BBoxRTree<T> prTree = jegeo::rtree::create_box_rtree(segPList);
    jegeo::bmodel::BBox<T> query_box = jegeo::rect::to_bbox(inter_rect);

    // 判断其中一个polygon在重合区域中的点是否在另一个polygon中
    jegeo::bmodel::BBoxResults<T> trResultSids;
    if (is_point_in_polygon_from_rect(query_box, polygon_a, segTList, trTree, segPList, prTree, trResultSids, consider_touch)) {
        return true;
    }

    // 判断剩下的一个polygon在重合区域中的点是否在另一个polygon中
    jegeo::bmodel::BBoxResults<T> prResultSids;
    if (is_point_in_polygon_from_rect(query_box, polygon_b, segPList, prTree, segTList, trTree, prResultSids, consider_touch)) {
        return true;
    }

    // 都没有点在对方多边形里面的话, 判断重合区域的双方是否有线段相交
    for (const auto &psid : prResultSids) {
        auto segp = segPList[psid.second];
        for (const auto &tsid : trResultSids) {
            auto segt = segTList[tsid.second];
            if (edge::is_line(segp) && edge::is_line(segt)) {
                Line<T> tmp_line_1 = line::make(edge::get_ps(segp), edge::get_pe(segp));
                Line<T> tmp_line_2 = line::make(edge::get_ps(segt), edge::get_pe(segt));
                if (intersects_segment2segment(tmp_line_1, tmp_line_2, consider_touch)) {
                    return true;
                }
            } else if (edge::is_line(segp) && edge::is_arc(segt)) {
                Line<T> tmp_line = line::make(edge::get_ps(segp), edge::get_pe(segp));
                Arc<T> tmp_arc = arc::make(edge::get_ps(segt), edge::get_pe(segt), edge::get_angle(segt));
                if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                    return true;
                }
            } else if (edge::is_arc(segp) && edge::is_line(segt)) {
                Line<T> tmp_line = line::make(edge::get_ps(segt), edge::get_pe(segt));
                Arc<T> tmp_arc = arc::make(edge::get_ps(segp), edge::get_pe(segp), edge::get_angle(segp));
                if (intersects_segment2monarc(tmp_line, tmp_arc, consider_touch)) {
                    return true;
                }
            } else if (edge::is_arc(segp) && edge::is_arc(segt)) {
                Arc<T> tmp_arc_1 = arc::make(edge::get_ps(segp), edge::get_pe(segp), edge::get_angle(segp));
                Arc<T> tmp_arc_2 = arc::make(edge::get_ps(segt), edge::get_pe(segt), edge::get_angle(segt));
                if (intersects_monarc2monarc(tmp_arc_1, tmp_arc_2, consider_touch)) {
                    return true;
                }
            }
        }
    }

    return false;
}

} // intersects

namespace contains {
using namespace polycollision_internal;

/*
* 判断 polygon_a 是否被包含在 polygon_b 里面
*/
template<typename T>
bool polygon_in_polygon(const Polygon<T> &polygon_a,
                                 const Polygon<T> &polygon_b,
                                 const Polygon<T> &polygon_bh,
                                 const std::vector<Edge<T>> &polya_segs,
                                 const jegeo::bmodel::BBoxRTree<T> &polya_rtree,
                                 const std::vector<Edge<T>> &polyb_segs,
                                 const jegeo::bmodel::BBoxRTree<T> &polyb_rtree,
                                 const std::vector<Edge<T>> &polybh_segs,
                                 const jegeo::bmodel::BBoxRTree<T> &polybh_rtree,
                                 bool consider_touch = true)
{
    Rect<T> arect = polygon::get_bound_rect(polygon_a);
    Rect<T> brect = polygon::get_bound_rect(polygon_b);

    if (!contains_rect_in_rect(arect, brect, consider_touch)) {
        return false;
    }

    bool hasHole = false;
    if (!polygon_bh.empty()) {
        hasHole = true;
    }

    // 先判断 inter_rect 的 4 个点是否全都在 polygon_b 里面
    const auto &polyb_bbox = polygon::get_bound_rect(polygon_b);
    Point<T> atmp_1 = point::make(jegeo::px1(arect), jegeo::py1(arect));
    Point<T> atmp_2 = point::make(jegeo::px1(arect), jegeo::py2(arect));
    Point<T> atmp_3 = point::make(jegeo::px2(arect), jegeo::py1(arect));
    Point<T> atmp_4 = point::make(jegeo::px2(arect), jegeo::py2(arect));
    if (!(is_point_in_polygon(atmp_1, polygon_b, polyb_bbox, polyb_segs, polyb_rtree, consider_touch)
            && is_point_in_polygon(atmp_2, polygon_b, polyb_bbox, polyb_segs, polyb_rtree, consider_touch)
            && is_point_in_polygon(atmp_3, polygon_b, polyb_bbox, polyb_segs, polyb_rtree, consider_touch)
            && is_point_in_polygon(atmp_4, polygon_b, polyb_bbox, polyb_segs, polyb_rtree, consider_touch))) {
        // polygon_a 中的所有点和边全都包含在 polygon_b 里面, 且 polygon_a 不会与 polygon_bh 发生碰撞视为包含
        for (auto seg : polya_segs) {
            if (!is_segment_in_polygon(seg, polygon_b, polyb_segs, polyb_rtree, consider_touch)) {
                return false;
            }
        }
    }

    if (hasHole && intersects::polygon2polygon(polygon_a, polygon_bh, polya_segs, polya_rtree, polybh_segs, polybh_rtree, false)) {
        return false;
    }

    return true;
}

/*
* 判断 polygon_a 是否被包含在 polygon_b 里面
*/
template<typename T>
bool polygon_in_polygon(const Polygon<T> &polygon_a, const Polygon<T> &polygon_b, bool consider_touch = true)
{
    Rect<T> arect = polygon::get_bound_rect(polygon_a);
    Rect<T> brect = polygon::get_bound_rect(polygon_b);

    if (!contains_rect_in_rect(arect, brect, consider_touch)) {
        return false;
    }

    Polygon<T> polygon_bh;
    bool hasHole = false;
    for (const auto &polyline : polygon_b) {
        if (polyline::is_hole(polyline)) {
            polygon_bh.push_back(polyline);
            hasHole = true;
        }
    }

    // polygon_b 构建树
    std::vector<Edge<T>> segList;
    for (auto seg : polygon::get_edges(polygon_b, true)) {
        segList.push_back(seg);
    }
    jegeo::bmodel::BBoxRTree<T> rtree = jegeo::rtree::create_box_rtree(segList);

    // 先判断 inter_rect 的 4 个点是否全都在 polygon_b 里面
    const auto &polyb_bbox = polygon::get_bound_rect(polygon_b);
    Point<T> atmp_1 = point::make(jegeo::px1(arect), jegeo::py1(arect));
    Point<T> atmp_2 = point::make(jegeo::px1(arect), jegeo::py2(arect));
    Point<T> atmp_3 = point::make(jegeo::px2(arect), jegeo::py1(arect));
    Point<T> atmp_4 = point::make(jegeo::px2(arect), jegeo::py2(arect));
    if (!(is_point_in_polygon(atmp_1, polygon_b, polyb_bbox, segList, rtree, consider_touch)
            && is_point_in_polygon(atmp_2, polygon_b, polyb_bbox, segList, rtree, consider_touch)
            && is_point_in_polygon(atmp_3, polygon_b, polyb_bbox, segList, rtree, consider_touch)
            && is_point_in_polygon(atmp_4, polygon_b, polyb_bbox, segList, rtree, consider_touch))) {
        // polygon_a 中的所有点和边全都包含在 polygon_b 里面, 且 polygon_a 不会与 polygon_bh 发生碰撞视为包含
        for (auto seg : polygon::get_edges(polygon_a, true)) {
            if (!is_segment_in_polygon(seg, polygon_b, segList, rtree, consider_touch)) {
                return false;
            }
        }
    }

    if (hasHole && jegeo::intersects::polygon2polygon(polygon_a, polygon_bh, false)) {
        return false;
    }

    return true;
}

} // contains

} // jegeo

#endif // JEGEO_POLYCOLLISION_HPP
